「拿起刀無法擁抱你，放下刀無法守護你。」——久保帶人

在正式開始講最長遞增子序列前先來玩個遊戲吧。

遊戲規則

我會用以下代碼隨機生成7項的陣列：

const arr = []
for(let i=0;i<7;i++) arr.push(Math.random() * 10 | 0)

然後我們要去找出這個陣列的子序列中，遞增，且長度最長的子序列索引。

例如我現在執行代碼生成了一個陣列arr為[0, 4, 3, 6, 6, 0, 5]。它遞增的子序列如下：
[0,4,6]
[0,3,6]
[0,6]
[0,5]
[4,6]
[4,5]
[3,6]
[3,5]
[0,5]

最長的是長度為3的子序列[0,4,6]及[0,3,6]，以[0,4,6]為例，它的各項分別對應arr的第0、1、3項，因此[0,1,3]就是一個arr的最長遞增子序列索引。

遊戲開始！

第一題隨機生成的陣列arr是——[4, 3, 7, 7, 5, 0, 6]！

讓我們來試著找出它的最長遞增子序列吧。

首先它的第0項是4，第1項是3，3比4小，所以4就先不考慮了。接著是連兩個7，7比3大，因此[3,7]可能是arr的最長遞增子序列的開頭。然後我們看到它的下一項是5，5比7小，因此[3,5]比[3,7]更有可能成為arr的最長遞增子序列。再來我們看到的是0，0比3和5都來的更小，因此最長遞增子序列的開頭有可能是[3,5]，也有可能是[0]。最後一項是6，我們便能找到最長遞增子序列就是[3,5,6]。

而3是arr的第1項，5是第4項，6是第7項，所以答案就是[1,4,7]。是不是跟你想的一樣呢？

我們再來做一題吧。第二題隨機生成的陣列arr是——[1, 1, 9, 0, 6, 1, 0]！

這一題能找到很多遞增子序列，但長度最長也就只有2，像是[1,9]，所以答案就是[1,9]的索引，也就是[0,2]。

再來做最後一題吧。第三題隨機生成的陣列arr是——[6, 2, 8, 0, 3, 3, 6]！

這一題我們人工遍歷完arr的前三項時，本來我們以為最長遞增子序列可能是[2,8]開頭，但沒想到後來出現的[0,3,6]的長度反超過了[2,8]，因此答案並不是[2,8]的索引，而是[0,3,6]的索引，[3,4,7]。

這一題是個不錯的例子，回想一下你是怎麼解出這道題的吧。你是不是也跟我一樣，在心裡記著目前可能是最長的遞增子序列有幾項，當看到第4項0的時候，你記著[2,8]的長度是2，然後開始算從0開始的遞增子序列能有多長，最後發現[0,3,6]的長度來到了3，所以不用再繼續記著[2,8]，答案就是[0,3,6]的索引，[3,4,7]。

策略與延伸問題

當然，這也是一個能解決問題的好方法。以這題為例，如果把上述策略寫成代碼，我們會先在內存開兩個陣列，一個用來儲存目前長度最高紀錄的遞增子序列，其它用來儲存目前遍歷到的遞增子序列。但我們之所以能只開兩個陣列，是因為這題arr的長度僅有7，而且數字還算容易處理。

如果今天arr長這樣——[6,7,8,9,5,6,7,8,4,5,6,7,1,2,3,4,5]，當我們遍歷前四項，我們發現最長遞增子序列可能是[6,7,8,9]開頭；但當我們又遍歷了4項，我們發現好像也有可能是[5,6,7,8]開頭；然後我們又遍歷了4項，我們發現[4,5,6,7]也是候補之一；最後我們遍歷完了整個arr，發現最長遞增子序列竟他牛腩的是[1,2,3,4,5]。

在找出[1,2,3,4,5]之前，我們很苦逼地用了3個陣列來存儲最長遞增子序列的候補。如果arr更長，甚至我們不限制它的每一項都只能是0~9，我們需要拿來存候補的陣列會越來越多，發散增長，顯然這個策略在效能上的消耗是比較大的。

那麼有沒有辦法不在內存上開那麼多個陣列來解決這個問題呢？當然是有的。尤雨溪的團隊在開發vue的時候，就在diff算法裡面使用了一套名為最長遞增子序列的算法，來解決這個同名問題。這套算法，能確保只在內存開兩個陣列便能解決這個問題。

試著想想看吧，你能不能也用更低的空間複雜度，找到一個陣列的最長遞增子序列索引？明天我們就來看看尤雨溪的團隊是怎麼做的，跟你的答案一不一樣:3